/**
 * @author: shiding
 * @data: 2022/5/25 16:51
 **/
public class MergeTwoLists {

    public static void main(String[] args) {
        ListNode list1 = new ListNode(1, new ListNode(2, new ListNode(3, null)));
        ListNode list2 = new ListNode(1, new ListNode(3, new ListNode(4, null)));
        ListNode listNode = mergeTwoLists(list1, list2);
        mergeTwoLists(list1, list2);
    }


    /**
     * 21. 合并两个有序链表
     * 建个意义上 可能不算是双指针
     * 定义一个新的链表，用于存放数据
     * 定义新的链表节点地址
     * 循环进行节点比较： （只要两个链表链表都不为空时进行循环）
     *    1、进行节点比较，小的那个 加入 新的链表 并 节点并向后移动
     *    2、新链表的节点，也向后移动
     *
     *  只要一个存在 空 则任务一个链表的数据 已经迁移完毕，并且 剩下链表中的数据一定是大于 之前迁移的数据的
     *
     * @param list1
     * @param list2
     * @return
     */
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        // 一个链表的算法题中是很常见的「虚拟头结点」技巧
        ListNode temp = new ListNode(-1);
        ListNode p = temp;
        ListNode p1 = list1;
        ListNode p2 = list2;
        while (p1 !=null && p2 != null) {
            if (p1.val < p2.val) {
                p.next = p1;
                p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;

        }
        if (p1 != null) {
            p.next = p1;
        }
        if (p2 != null) {
            p.next = p2;
        }
        return temp.next;
    }



}


class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}